package com.sx.sx1.lintcode.day717;

import java.util.*;


public class LC249 {

    static class Solution {
        /**
         * @param a: an integer array
         * @return: A list of integers includes the index of the first number and the index of the last number
         */

        public List<Integer> countOfSmallerNumberII(int[] a) {
            List<Integer> ans = new ArrayList<>();
            SegmentNode tree = buildTree(0, 10000);
            for (int item : a) {
                updatetree(tree, item); //更新线段树
                if(item ==0){
                    ans.add(0);
                    continue;
                }
                int cur = querytree(tree, 0, item - 1); //查询前面比自己小的数的个数
                ans.add(cur);
            }
            return ans;
        }

        public int querytree(SegmentNode node, int start, int end) {
            if (start <= node.start && end >= node.end) {
                return node.data;
            }

            int m = node.start + ((node.end - node.start) >> 1);
            int left = 0;
            int right = 0;
            if (m >= start) {
                left = querytree(node.left,start,Math.min(m,end));
            }

            if (m < end) {
                right = querytree(node.right,m>=start?m+1:start,end);
            }

            return left+right;
        }

        public void updatetree(SegmentNode node, int idx) {
            if (node.start == node.end && node.start == idx) {
                node.data += 1;
                return;
            }

            int m = node.start + ((node.end - node.start) >> 1);
            if (m >= idx) {
                updatetree(node.left, idx);
            } else {
                updatetree(node.right, idx);
            }

            node.data = node.left.data + node.right.data;
        }

        public SegmentNode buildTree(int start, int end) {
            if (start == end) {
                return new SegmentNode(start, end);
            }
            SegmentNode root = new SegmentNode(start, end);
            int m = start + ((end - start) >> 1);
            root.left = buildTree(start, m);
            root.right = buildTree(m + 1, end);
            return root;
        }

        static class SegmentNode {
            public int start, end, data;
            public SegmentNode left, right;

            public SegmentNode(int s, int e) {
                start = s;
                end = e;
            }
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        int[] arr3 =  new int[]{73,82,74,12,25,0,33,46,79,90,6,97,18,84,34,54,64,5,54,44,74,95,90,24,70,94,12,41,79,88,48,82,89,100,33,3,23,21,90,50,26,3,4,21,67,24,59,62,9,78,60,40,4,40,7,5,54,38,68,66};
        int[] arr2 =  new int[]{73,82,74,12,25,0,33,46,79,90,6,97,18,84,34,54,64,5,54,44,74,95,90,24,70,94,12,41,79,88,48,82,89,100,33,3,23,21,90,50,26,3,4,21,67,24,59,62,9,78,60,40,4,40,7,5,54,38,68,66};
        int[] arr =  new int[]{73,82,74,12,25,0,33,46,79};
       // System.out.println(obj.countOfSmallerNumberII(new int[]{1, 2, 7, 8, 5}));
       // System.out.println(obj.countOfSmallerNumberII(new int[]{7, 8, 2, 1, 3}));
        System.out.println(obj.countOfSmallerNumberII(
             arr));
    }
}

/*

输入数据
[73,82,74,12,25,0,33,46,79,90,6,97,18,84,34,54,64,5,54,44,74,95,90,24,70,94,12,41,79,88,48,82,89,100,33,3,23,21,90,50,26,3,4,21,67,24,59,62,9,78,60,40,4,40,7,5,54,38,68,66]
输出数据
[0,1,1,0,1,0,2,3,6,8,0,10,2,10,5,7,8,0,8,7,13,19,18,4,13,22,2,9,19,23,12,22,26,32,7,0,6,6,31,17,10,0,2,8,25,11,25,26,5,34,27,19,2,20,6,4,29,22,38,37]
期望答案
[0,1,1,0,1,0,3,4,7,9,1,11,3,11,6,8,9,1,9,8,14,20,19,5,14,23,3,10,20,24,13,23,27,33,8,1,7,7,32,18,11,1,3,9,26,12,26,27,6,35,28,20,3,21,7,5,30,23,39,38]
提示
Review your code and make sure your algorithm is correct. Wrong answer usually caused by typos if your algorithm is correct.
评测过程会影响此处显示的输出结果，但不会影响代码本身输出的值。
控制台
历史提交


样例
样例 1:

输入:
[1,2,7,8,5]
输出:
[0,1,2,3,2]
样例 2:

输入:
[7,8,2,1,3]
输出:
[0,1,0,0,2]
标签
 */
/*
https://blog.csdn.net/qq_40507857/article/details/83272803

用方法3：
思路3

通过缓存区间点的“比其小的数的个数”，从而舍弃部分已知小的数，使用类似二叉树的结构，遇小放左，遇大放右；那么a[i]元素在树中所有左节点的个数，即为a[i]前面小于比自己小的节点的个数

#include<bits/stdc++.h>
using namespace std;
#define nullptr NULL

class Solution {
public:
	struct node{
		int count=0;//小于data元素的个数
		int data=0;//数列元素
		int rep=0;//repeat，重复元素的个数
		node* left=nullptr;
		node* right=nullptr;
		node(int num){data=num;}
		~node(){
			if(left)	delete left;
			if(right)	delete right;
		}
	};

public:
    /**
     * @param A: an integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    /*
vector<int> countOfSmallerNumberII(vector<int> &A) {
    // write your code here
    int len=A.size();
    vector<int> res(len);
    res[0]=0;
    node* root=new node(A[0]);
    node* temp=nullptr;
    int count=0;
    for(int i=1;i<len;i++){
        temp=root;
        count=0;
        while(true){
            if(temp->data > A[i]){
                temp->count++;
                if(temp->left)
                    temp=temp->left;
                else{
                    temp->left=new node(A[i]);
                    break;
                }
            }else if(temp->data < A[i]){
                count+=(temp->count+temp->rep+1);
                if(temp->right){
                    temp=temp->right;
                }else{
                    temp->right=new node(A[i]);
                    break;
                }
            }else{
                count+=temp->count;
                temp->rep++;
                break;
            }
        }
        res[i]=count;
    }//for
    delete root;
    return res;
}
};
int main()
        {
        int n;
        while(scanf("%d",&n)!=EOF){
        vector<int> A(n);
        for(int i=0;i<n;i++)
        scanf("%d",&A[i]);

        Solution work;
        vector<int> res;
        res=work.countOfSmallerNumberII(A);

        for(int i=0;i<n;i++)
        {
        printf("%d",res[i]);
        if(i==n-1)
        printf("\n");
        else
        printf(" ");
        }
        }
        return 0;
        }
/*
5
1 2 7 8 5
*//*

        ————————————————
        版权声明：本文为CSDN博主「紫芝」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
        原文链接：https://blog.csdn.net/qq_40507857/article/details/83272803

 */
/*


}
/* int query(SegmentTreeNode * root,int start,int end,int q){  //查询特定区域比q小的个数
        if(root == nullptr) return 0;
        if(root->start > end || root->end < start) return 0;
        if(root->start >= start && root->end <= end && root->max<q) return root->end - root->start + 1;
        return query(root->left,start,end,q)+query(root->right,start,end,q);

————————————————
版权声明：本文为CSDN博主「紫芝」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40507857/article/details/83272803





 int buildTree(vector<int> &A,SegmentTreeNode * root){ //建立线段树，每个节点保存该区域内最大值
        int start = root->start;
        int end = root->end;
        if(start > end) return 0;
        if(start == end) {
            root->max = A[start];
            return A[start];
        }else{
            root->left = new SegmentTreeNode(start,(start+end)/2,INT_MIN);
            root->right = new SegmentTreeNode((start+end)/2+1,end,INT_MIN);
            int L_max = buildTree(A,root->left);
            int R_max = buildTree(A,root->right);
            root->max = L_max>R_max?L_max:R_max;
            return root->max;
        }
    }

    int query(SegmentTreeNode * root,int start,int end,int q){  //查询特定区域比q小的个数
        if(root == nullptr) return 0;
        if(root->start > end || root->end < start) return 0;
        if(root->start >= start && root->end <= end && root->max<q) return root->end - root->start + 1;
        return query(root->left,start,end,q)+query(root->right,start,end,q);
    }
};

————————————————
版权声明：本文为CSDN博主「紫芝」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_40507857/article/details/83272803

LintCode-Logo
学习
刷题
题集
群组
内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
您上个月的刷题报告已生成，点击查看
avatar
249 · 统计前面比自己小的数的个数
算法
困难
通过率
28%
题目
题解34
笔记99+
讨论1
排名
记录
描述
给定一个整数数组（下标由 0 到 n-1， n 表示数组的规模，ai的取值范围由 0 到10000）。对于数组中的每个 ai 元素，请计算 ai 前的数中比它小的元素的数量，并返回数量数组。

北美在招WLB&高薪厂面经曝光

微信加sunny【jiuzhang1104】备注【在招】即可领取


在做此题前，我们建议你先完成以下三道题: 线段树的构造， 线段树的查询 II，和 统计比给定整数小的数的个数 。

样例
样例 1:

输入:
[1,2,7,8,5]
输出:
[0,1,2,3,2]
样例 2:

输入:
[7,8,2,1,3]
输出:
[0,1,0,0,2]
标签
相关题目

248
统计比给定整数小的数的个数
中等
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
245/3007
已开启智能提示
发起考试
45 分 00 秒
123456789
public class Solution {
    /**
     * @param a: an integer array
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    /*
public List<Integer> countOfSmallerNumberII(int[] a) {
    // write your code here
}
}
控制台
        历史提交

 */


/*
[73,82,74,12,25,0,33,46,79,90,6,97,18,84,34,54,64,5,54,44,74,95,90,24,70,94,12,41,79,88,48,82,89,100,33,3,23,21,90,50,26,3,4,21,67,24,59,62,9,78,60,40,4,40,7,5,54,38,68,66]
期望答案
[0,1,1,0,1,0,3,4,7,9,1,11,3,11,6,8,9,1,9,8,14,20,19,5,14,23,3,10,20,24,13,23,27,33,8,1,7,7,32,18,11,1,3,9,26,12,26,27,6,35,28,20,3,21,7,5,30,23,39,38]
 */
